package 栈;

import java.util.Stack;

public class Demo01 {
    static class Solution {
        public boolean isValid(String s) {
            Stack<Character> stack = new Stack<>();
            for(int i = 0; i<s.length(); i++){
                char c = s.charAt(i);
                if(stack.isEmpty() &&(c == '(' || c == '{' || c == '[')){
                    stack.push(c);
                }else{
                    if((stack.peek() == '(' && c == ')')||(stack.peek() == '[' && c == ']')||(stack.peek() == '{' && c == '}')){
                        stack.pop();
                    }else{
                        return false;
                    }
                }
            }
            return stack.isEmpty();
        }
    }

    /*
    * 改进: 建立哈希表 dic 构建左右括号对应关系：key 左括号，value 右括号；
    * 这样查询 2 个括号是否对应只需 O(1) 时间复杂度；建立栈 stack，遍历字符串 s 并按照算法流程一一判断。
    * */
}
